#include<iostream>
namespace MYSPACE{
enum Color{
  RED = 0,
  BLACK
};
template<class K,class V>
class TreeNode{
public:
  TreeNode(const std::pair<K,V>& data):
    _parent(nullptr),
    _left(nullptr),
    _right(nullptr)
  {
    _data.first = data.first;
    _data.second = data.second;
  }
public:    
  std::pair<K,V> _data;
  TreeNode* _parent;
  TreeNode* _left;
  TreeNode* _right;
  Color _color; 
};
template<class K,class V>
class RBTree{
  public:
  RBTree():_root(nullptr){}

  public:
  void print()
  {
    _print(_root);
  }
  bool IsRBTree()
  {
    int Bcount = 0,anycount = 0;
    TreeNode<K,V>* node = _root;
    while(node)
    {
      if(node->_color == BLACK)
      {
        Bcount++;
      }
      node = node->_left;
    }
    if(_IsRBTree(_root,Bcount,anycount))
    {
      return true;
    }
    else{
      return false;
    }
  }

  void insert(const std::pair<K,V> data)
  {
    if(_root == nullptr)
    {
      _root = new TreeNode<K,V>(data);
      _root->_color = BLACK;
      return;
    }
    TreeNode<K,V>* parent = nullptr;
    TreeNode<K,V>* now_node = _root;
    while(now_node)
    {
      parent = now_node;
      if(now_node->_data.first > data.first)
      {
        now_node = now_node->_left;
      }
      else if(now_node->_data.first < data.first)
      {
        now_node = now_node->_right;
      }
      else{
        return;
      }
    }
    TreeNode<K,V>* newnode = new TreeNode<K,V>(data);
    if(parent->_data.first > data.first)
    {
      parent->_left = newnode;
    }
    else if(parent->_data.first < data.first)
    {
      parent->_right = newnode;
    }
    else{
      std::cerr << "error" << std::endl;
      exit(1);
    }
    newnode->_color = RED;
    newnode->_parent = parent;
  //开始调整
  //如果父亲颜色为黑 || parent== nullptr 则不管
    if(parent && parent->_color == RED)
    {
      Adjust(newnode);
    }
  }
  private:
  void Adjust(TreeNode<K,V>* node)
  {
    TreeNode<K,V>* parent = node->_parent;
    TreeNode<K,V>* grandparent = parent->_parent;
    TreeNode<K,V>* uncle = nullptr; 
    //如果父亲颜色为黑 || parent== nullptr 则不管
    while(parent && parent->_color == RED)
    {
      if(parent == grandparent->_left)
      {
        uncle = grandparent->_right;
        if(grandparent->_right == nullptr || uncle->_color == BLACK)
        {
          if(parent->_right == node)
          {
            //变色双旋
            //左右双旋
            LevoRotate(node);
            DextroRotate(node);
            grandparent->_color = RED;
            node->_color = BLACK;
            if(grandparent == _root)
            {
              _root = node;
            }
            break;
          }
          else if(parent->_left == node)
          {
            //变色单旋
            //右旋
            DextroRotate(parent);
            //adjust _color
            parent->_color = BLACK;
            grandparent->_color = RED;
            if(grandparent == _root)
            {
              _root = parent;
            }
            break;
          }
        }
        else if(uncle->_color == RED)
        {
          parent->_color = BLACK;
          uncle->_color = BLACK;
          grandparent->_color = RED;
        }
      }
      else if(parent == grandparent->_right)
      {
        uncle = grandparent->_left;
        if(grandparent->_left == nullptr || uncle->_color == BLACK)
        {
          if(parent->_right == node)
          {
            //变色单旋
            //左旋
            LevoRotate(parent);
            parent->_color = BLACK;
            grandparent->_color = RED;
            if(grandparent == _root)
            {
              _root = parent;
            }
            break;
          }
          else if(parent->_left == node)
          {
            //变色双旋
            //右左双旋
            DextroRotate(node);
            LevoRotate(node);
            grandparent->_color = RED;
            node->_color = BLACK;
            if(grandparent == _root)
            {
              _root = node;
            }
            break;
          }

        }
        else if(uncle->_color == RED)
        {
          parent->_color = BLACK;
          uncle->_color = BLACK;
          grandparent->_color = RED;
        }

      }
      node = grandparent;
      parent = node->_parent;
      if(parent)
      grandparent = parent->_parent;
    }
    if(_root)
    {
      _root->_color = BLACK;
    }
  }
  void DextroRotate(TreeNode<K,V>* node)
  {
    TreeNode<K,V>* parent = node->_parent;
    TreeNode<K,V>* grandparent = parent->_parent;
    TreeNode<K,V>* Rnode = node->_right;
    //adjust _left || _right
    node->_right = parent;
    parent->_left = Rnode;
    //adjust grandparent
    if(grandparent && grandparent->_left == parent)
    {
      grandparent->_left = node;
    }
    else if(grandparent && grandparent->_right == parent){
      grandparent->_right = node;
    }
    //adjust _parent
    node->_parent = grandparent;
    parent->_parent = node;
    if(Rnode)
    Rnode->_parent = parent;
  }
  void LevoRotate(TreeNode<K,V>* node)
  {
    TreeNode<K,V>* parent = node->_parent;
    TreeNode<K,V>* grandparent = parent->_parent;
    TreeNode<K,V>* Lnode = node->_left;
    //adjust _left || _right
    node->_left = parent;
    parent->_right = Lnode;
    //adjust grandparent
    if(grandparent && grandparent->_left == parent)
    {
      grandparent->_left = node;
    }
    else if(grandparent && grandparent->_right == parent)
    {
      grandparent->_right = node;
    }
    //adjust _parent
    node->_parent = grandparent;
    parent->_parent = node;
    if(Lnode)
    Lnode->_parent = parent;
  }
  private:
  bool _IsRBTree(TreeNode<K,V>* root,int Bcount,int anycount)
  {
    if(root == nullptr)
    {
      if(Bcount != anycount)
      {
        std::cout << "Bcout:" << Bcount << " anycount:" << anycount << std::endl;
        return false;
      }
      else{
        return true;
      }
    }
    if(root->_color == BLACK)
    {
      ++anycount;
    }
    return _IsRBTree(root->_left,Bcount,anycount) &&
    _IsRBTree(root->_right,Bcount,anycount);
  }
  void _print(TreeNode<K,V>* root)
  {
    if(root == nullptr)
    {
      return;
    }
    _print(root->_left);
    std::cout << root->_data.first << " " << root->_data.second << std::endl;
    _print(root->_right);
  }
  private:
  TreeNode<K,V>* _root;
};


}

